package com.changanw.code17;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author changanw
 * @version
 * @description 电话号码的字母组合   回溯方式解决
 * @date 2023/7/3 21:58
 */
public class Code17 {
  public List<String> letterCombinations(String digits) {
    List<String> res = new ArrayList<>();
    if (digits.length() == 0) {
      return res;
    }
    Map<Character,String> map = new HashMap<>();
    map.put('2', "abc");
    map.put('3', "def");
    map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");
    backtrack(res, map, digits, 0, new StringBuffer());
    return res;


  }
  public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
    if (index == digits.length()) {
      combinations.add(combination.toString());
    } else {
      char digit = digits.charAt(index);
      String letters = phoneMap.get(digit);
      int lettersCount = letters.length();
      for (int i = 0; i < lettersCount; i++) {
        combination.append(letters.charAt(i));
        backtrack(combinations, phoneMap, digits, index + 1, combination);
        combination.deleteCharAt(index);
      }
    }
  }

  public static void main(String[] args) {
    Code17 code17 = new Code17();
    List<String> strings = code17.letterCombinations("23");
    System.out.println(strings.toString());
  }
}
